package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 寻找重复的子树562.java
 * @Description https://leetcode-cn.com/problems/find-duplicate-subtrees/
 * @createTime 2021年06月28日 19:11:00
 */
public class 寻找重复的子树562 {

    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> list = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) {
            return list;
        }
        collect(root);
        return list;
    }

    private String collect(TreeNode root) {
        if (root == null) {
            return "#";
        }
        String val = root.val + "," + collect(root.left) + "," + collect(root.right);
        map.put(val, map.getOrDefault(val, 0) + 1);
        if (map.getOrDefault(val,0) == 2) {
            list.add(root);
        }
        return val;
    }
}
